#include "leecode.h"
#include "limits.h"

class Solution {
public:
    int jump(vector<int>& nums) {
      int len = nums.size();
      if(len == 1)
        return 0;
      else if(len == 2 && nums[0] == 0)
        return 0; 
      steps_[1] = 0;
      steps_[2] = 1;
      int ret = jumpImpl(nums, len);
      if(ret == INT_MAX)
        return 0;
      return ret;
    }

    int jumpImpl(vector<int>& nums, int len) {
      auto iter = steps_.find(len);
      if(iter != steps_.end())
        return iter->second;

      int min_step = INT_MAX;
      for(int i = 0; i <= len-2 ; i++) {
        int distance = len - i -1;
        if(distance > nums[i])
          continue;
        else {
          int temp = jumpImpl(nums, i+1);
          if(temp == INT_MAX)
            continue;
          temp = temp + 1;
          min_step = temp < min_step? temp: min_step;
        }
      }
//      steps_[len] = min_step;
      steps_.insert({len, min_step});
      printf("step %d is %d\n", len, min_step);
      return min_step;
    }
    unordered_map<int, int> steps_;
};

TEST(jump, jump) {
  GTEST_SKIP();
  vector<int> v1{2,3,1,1,4};
  EXPECT_EQ(Solution().jump(v1), 2);

  vector<int> v2{2,3,0,1,4};
  EXPECT_EQ(Solution().jump(v2), 2);

  vector<int> v3{3, 2, 1};
  EXPECT_EQ(Solution().jump(v3), 1);
}